Monster Media 1996 #15/Monster Media Number 15 (Monster Media)(July 1996).ISO/internet/javnl005.zip/JAVNL005.TXT

Text File | 1996-05-14 | 16KB | 510 lines

Issue #005
May, 1996


Contents:

Comparing C/C++ with Java Part 5 - Multiple Inheritance
Sorting in Java
Java Program Packaging Part 3 - Protected/Default
Performance - Method Call Overhead


COMPARING C/C++ WITH JAVA PART 5 - MULTIPLE INHERITANCE

Suppose that you have two C++ classes:

        class A {
        public:
                int x;
                void f();
        };

        class B {
        public:
                int y;
                void g();
        };

and a third class that derives or inherits ("extends") from both of
these:

        class C : public A, public B {
                // stuff
        };

Inheriting from multiple base classes is called "multiple inheritance"
or MI for short.

Like templates that we discussed in issue #004, multiple inheritance
adds to the complexity of C++, while offering a solution to some
particular kinds of programming problems.  One type of issue with
programming using MI is in deciding which of a set of conflicting
inherited names "wins".

Java does not have multiple inheritance.  It does, however, have a way
of doing some of what MI is intended for, relative to inheriting
attributes.  In Java there is a language feature called an interface,
which looks like this:

        public interface Orderable {
                // return < 0 if p1 < p2, 0 if equal, > 0 if p1 > p2
                public int compareTo(Object p1, Object p2);
        }

This looks somewhat like a class, except that all the methods are
abstract, that is, are not implemented immediately but serve as
placeholders.

What is an interface used for?  Suppose that you want to ensure that a
particular class has certain properties, in the present case that it
defines the method compareTo() to order objects.  You can enforce this
by requiring that the class implement interface Orderable:

        public class xxx implements Orderable {
                public int compareTo(Object p1, Object p2)
                {
                        int n1 = ((Integer)p1).intValue();
                        int n2 = ((Integer)p2).intValue();
                        return n1 - n2;
                }
        }

Why do we care about this?  In the next section we will talk about
sorting in Java.  To write a semi-general sort method, it's necessary
to assume that the objects within a Vector of objects to be sorted
have some ordering method available to rank them.  Java by default has
no way of ordering two arbitrary objects.

By defining an Orderable interface, and either sorting a vector of
Orderables (that is, a vector of object types where the type is
defined to implement Orderable), or sorting a Vector of Objects with a
compareTo() method passed to the sort routine via a method wrapper
(see next section), we can ensure that a compareTo() method is
available.

An interface is sort of like a base class for a class.  If you have
an Orderable reference:

        Orderable or = null;

it's possible to assign to it a reference to an object type that
implements Orderable:

        xxx x = new xxx();

        or = x;

Again, if we have an Orderable object reference, we can be sure that a
method call like:

        or.compareTo(p1, p2)

will be valid.


SORTING IN JAVA

In the last issue we talked about sorting in Java and said that
there's no approach to sorting that's really similar to qsort() in
C/C++.  A couple of people wrote to me about this and suggested a
technique that does in fact have some similarities.

The idea is to write a sort method that accepts a Vector of Object
references, along with a class object instance that is a wrapper for a
compareTo() method as illustrated above.  The sort routine will
iterate over the vector and call out to the compare method to
determine the ordering of any two objects.  Specifically, this would
look like:

        import java.util.Vector;

        // Orderable interface

        interface Orderable {
                // return < 0 if p1 < p2, 0 if equal, > 0 if p1 > p2
                public int compareTo(Object p1, Object p2);
        };

        // wrapper for a compareTo() method for ordering Strings

        class Ord implements Orderable {
                public int compareTo(Object p1, Object p2)
                {
                        return ((String)p1).compareTo(((String)p2));
                }
        }

        public class Sort {

                public static void sort(Vector v, Orderable or)
                {
                        if (v == null || or == null)
                                ; // give error of some kind

                        // get vector size

                        int n = v.size();

                        // sort

                        for (int i = 0; i < n - 1; i++) {
                                for (int j = i + 1; j < n; j++) {

                                        // do comparison

                                        if (or.compareTo(v.elementAt(i),
                                            v.elementAt(j)) > 0) {
                                                Object ti = v.elementAt(i);
                                                Object tj = v.elementAt(j);
                                                v.setElementAt(tj, i);
                                                v.setElementAt(ti, j);
                                        }
                                }
                        }
                }

                // driver program

                public static void main(String args[])
                {
                        Vector v = new Vector();
                        int N = 100;
                        int i = 0;

                        // add some strings

                        for (i = 0; i < N; i++)
                                v.addElement("xxx" + i);

                        // sort them

                        Sort.sort(v, new Ord());

                        // display the sorted list

                        for (i = 0; i < N; i++)
                                System.out.println((String)v.elementAt(i));
                }

        }

This code can be tuned in various ways (starting with the sort
algorithm) but is illustrative of the technique.  We can implement any
sort strategy we want on a Vector of objects simply by changing the
ordering method.  For example, saying:

        class Ordrev implements Orderable {
                public int compareTo(Object p1, Object p2)
                {
                        return -((String)p1).compareTo(((String)p2));
                }
        }

        ...

        Sort.sort(v, new Ordrev());

will reverse the sorting order for Strings.  In this particular
example, Strings have a compareTo() method already defined, and we
simply cast the Object references to Strings and call this method.
Note that if the wrong compareTo() wrapper instance is used, then an
illegal cast will be attempted, resulting in an exception being
thrown.  For example, the above case expects a String, and will
generate an exception ("ClassCastException") if the objects we pass in
are actually Integers.  The "instanceof" operator can be used to help
sort things out.

In production code we'd have Orderable defined in a separate source
file.  Ord might or might not be in its own file, depending on
stylistic preferences.  Ord is simply a wrapper for a particular
compareTo() method.  In C or C++ we would pass in a function pointer
directly, but Java has no user-visible pointers and no global
functions.

If we critique this approach and compare it to qsort(), there are some
notable differences and some similarities:

        1.  This approach is higher-level than qsort(), because it
        doesn't fool with pointers and sizes of objects and so on.

        2.  This approach cannot be used to directly sort vectors of
        fundamental data types like int or double.  They must be
        sorted using object wrappers.

        3.  Both approaches require calling out to a function or
        method that is used to order elements.  Such calls are
        expensive.

        4.  This approach has some overhead in accessing and setting
        Vector element slots.  There is method call overhead, as well
        as the subscript range checking done each time within a method
        like elementAt().

It's possible to write a similar type of method for doing binary
searches, kind of like bsearch() in the C library.


JAVA PROGRAM PACKAGING PART 3 - PROTECTED/DEFAULT

In issue #004 we talked about public and private fields.  When public
is applied to a method or variable:

        public int x = 37;

        public void f() {}

it means that the method or variable is visible everywhere, while a
private method or variable:

        private int x = 37;

        private void f() {}

is visible only within the class where it is defined.

Two other levels of visibility are protected:

        protected int x = 37;

and the default when no keyword is specified:

        void f() {}

These are identical except in one case.  For both of these levels, the
method or variable is visible in the class where it's defined and to
subclasses and non-subclasses from the same package.  For example:

        // file pack1/A.java

        package pack1;

        public class A {
                protected int x = 0;
                int f() {return x;}
                public static void main(String args[]) {}
        }

        class B extends A {
                void g()
                {
                        A p = new A();
                        int i = p.x + p.f();
                }
        }

        class C {
                void g()
                {
                        A p = new A();
                        int i = p.x + p.f();
                }
        }

while not being accessible from other packages:

        // file pack1/AA.java

        package pack1;

        public class AA {
                protected int x = 0;
                int f() {return x;}
                public static void main(String args[]) {}
        }

        // file pack2/BB.java

        package pack2;

        import pack1.AA;

        class BB extends AA {
                void g()
                {
                        AA p = new AA();
                        int i = p.x + p.f(); // error here
                }
        }

        class CC {
                void g()
                {
                        AA p = new AA();
                        int i = p.x + p.f(); // error here
                }
        }

Where protected and the default differ is in whether they are
inherited by a subclass in a different package.  For example:

        // file pack1/D.java

        package pack1;

        public class D {
                int x = 37;
                protected int y = 47;
                public static void main(String args[]) {}
        }

        // file pack2/E.java

        package pack2;

        import pack1.D;

        class E extends D {
                void f()
                {
                        int i = x;              // error here
                        int j = y;              // OK here
                }
        }

There are a couple more issues with packaging that we will explore in
future issues.


PERFORMANCE - METHOD CALL OVERHEAD

In a language such as C or C++ you may have encountered the idea that
calling a function ("method" in Java) has some time overhead
associated with it beyond the actual processing done by the function.
For example, with this code:

        int max(int a, int b)
        {
                return (a > b ? a : b);
        }

        int main()
        {
                int i = 0;
                int j = 0;
                int k = 0;
                long n = 50000000L;
                while (n-- > 0)
                        //k = max(i, j);
                        k = (i > j ? i : j);

                return 0;
        }

coding the actual calculation of the maximum of two ints is about
three times as fast when done inline as when done via a call to
max().  In C++ there is an "inline" specifier that can be used to
specify that a function should be expanded inline if possible.

Function call overhead is caused by various factors, including time
spent in setting up stack frames, actual transfer of control to the
called function, and so on.

Java also has overhead with calling methods.  For example, in this
code:

        public class xx {

                public /*final*/ int max(int a, int b)
                {
                        return (a > b ? a : b);
                }

                public static void main(String args[])
                {
                        int i = 0;
                        int j = 0;
                        int k = 0;
                        int n = 1000000;
                        xx p = new xx();

                        while (n-- > 0)
                                //k = p.max(i, j);
                                k = (i > j ? i : j);
                }

        }

doing the max computation inline is about twice as fast as calling the
method max().

In Java one reason for overhead is that methods are virtual by
default, that is, the actual method that is called is determined at
run time by considering the actual object type.  For example, the
Object class, from which all other class types derive, has a method
hashCode() defined in it.  A class that extends from Object may also
have a hashCode() method.  If in a program you have an Object
reference, and wish to call hashCode():

        public void f(Object p)
        {
                int h = p.hashCode();
        }

then the actual version of hashCode() that is called depends on
whether p is "really" an Object or refers to an instance of a class
derived from Object.

So, because a method is virtual by default, it is difficult or
impossible to expand it as inline (in C++ there have been some clever
optimizations that have been used to make virtual functions inline,
but this is a hard problem).

The keyword "final" can be used to say "this method cannot be
overridden" by another method in a derived class.  With JDK 1.0 this
optimization has no effect, but over the long term specifying "final"
is likely to be an important optimization.  Note that "final" has
various other meanings, for example saying:

        final int N = 10;

marks N as unchangeable, and a final class cannot be extended from.

Should you worry about method call overhead?  Most of the time, no.
It's only when you have a method that's called very heavily in a loop
that this overhead matters.


ACKNOWLEDGEMENTS

Thanks to Thierry Ciot, Irv Kanode, Mike Paluka, and Alan Saldanha for
help with proofreading.


SUBSCRIPTION INFORMATION / BACK ISSUES

To subscribe to the newsletter, send mail to [e-mail]
with this line as its message body:

subscribe java_letter

Back issues are available via FTP from:

        rmii.com /pub2/glenm/javalett

or on the Web at:

        http://www.rmii.com/~glenm

There is also a C++ newsletter.  To subscribe to it, say:

subscribe c_plus_plus

using the same [e-mail] address.

-------------------------

Copyright (c) 1996 Glen McCluskey.  All Rights Reserved.

This newsletter may be further distributed provided that it is copied
in its entirety, including the newsletter number at the top and the
copyright and contact information at the bottom.

Glen McCluskey & Associates
Professional Computer Consulting
Internet: [e-mail]
Phone: [phone] or [phone]
Fax: [phone]
FTP: rmii.com /pub2/glenm/javalett (for back issues)
Web: http://www.rmii.com/~glenm